package com.data_structure_algorithm.data_structure.tree.huff;

import java.io.*;
import java.util.*;

/**
 * @Authror PABLO
 * @Date 2022/4/1 14:43
 * @Desc
 */
public class HuffZip {
    static HuffUpZip huffUpZip = new HuffUpZip();//解码

    public static void main(String[] args) throws Exception {

/*        Node node = new Node((byte) 102, 102);
        String str = "woaini heiheiheiheiehi"; //对应字节数组长度40
        //System.out.println("原始" + Arrays.toString(str.getBytes()));
        //str对应的编码后的字符数组
        byte[] huffmanCodes = new HuffZip().getHuffmanCodesZip();
        //System.out.println("编码" + Arrays.toString(huffmanCodes));
        //解码后的字节数组
        byte[] decode = huffUpZip.decode(huffmanCode, huffmanCodes);
        //System.out.println("解码" + Arrays.toString(decode));
        System.out.println();
         //System.out.println(new String(decode));*/

        HuffZip huffZip = new HuffZip();
        huffZip.compress("D:\\233.doc", "D:\\temp.zip");

        huffZip.decode("D:\\temp.zip","D:\\564965a0d8be2.doc");
    }

    /**
     * @Description: 文件解压
     * @Author: PABLO
     * @Date: 2022/4/2 21:44
     * @Params: [desFile 压缩文件, srcFile 解压后的文件]
     * @Return: void
     **/
    public void decode(String zipFile, String desFile) {


        //文件输入
        InputStream inputStream = null;

        ObjectInputStream objectInputStream = null;

        //文件输出

        OutputStream outputStream = null;


        try {
            inputStream = new FileInputStream(zipFile);

            objectInputStream = new ObjectInputStream(inputStream);

            byte[] huffmanBytes = (byte[]) objectInputStream.readObject();

            Map<Byte, String> huffmanCode = (Map<Byte, String>) objectInputStream.readObject();

            //调用解码方法
            byte[] decode = huffUpZip.decode(huffmanCode, huffmanBytes);

            //out
            outputStream = new FileOutputStream(desFile);
            //写数据
            outputStream.write(decode);

        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            try {
                inputStream.close();
                objectInputStream.close();
                outputStream.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

    }

    /**
     * @Description: 文件压缩
     * @Author: PABLO
     * @Date: 2022/4/2 20:47
     * @Params: [srcFile 源文件位置, desFile 压缩后的目标文件位置]
     * @Return: void
     **/
    public void compress(String srcFile, String desFile) {
        FileInputStream fileInputStream = null;
        FileOutputStream fileOutputStream = null;
        ObjectOutput objectOutput = null;
        try {
            fileInputStream = new FileInputStream(srcFile);
            byte[] bytes = new byte[fileInputStream.available()];
            //读取
            fileInputStream.read(bytes);

            //获取原文件对应的赫夫曼压缩后的字节数组
            byte[] huffmanCodesZip = getHuffmanCodesZip(bytes);

            //创建输出流
            fileOutputStream = new FileOutputStream(desFile);
            //为了后期回复源文件使用
            objectOutput = new ObjectOutputStream(fileOutputStream);
            //赫夫曼数组写入压缩文件
            objectOutput.writeObject(huffmanCodesZip);

            //将赫夫曼编码写入压缩文件，一遍后续恢复，恢复时需要赫夫曼编码才可以
            objectOutput.writeObject(huffmanCode);


        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            try {
                fileInputStream.close();
                fileOutputStream.close();
                objectOutput.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

    //存放字符和对应的编码
    static Map<Byte, String> huffmanCode = new HashMap<>();
    //拼接某个叶子结点的路径即10101010
    static StringBuilder stringBuilder = new StringBuilder();

    //可重载
    public byte[] getHuffmanCodesZip(byte[] content) {

        //将字节数组转为list
        List<Node> list = convert(content);
        //根据list获取哈夫曼树
        Node huffmanList = getHuffmanTreeByList(list);
        //将赫夫曼树对应编码表示出来
        Map<Byte, String> huffCodes = getCodes(huffmanList);
        //生成编码数据
        byte[] huffmanCodeBytes = zip(content, huffCodes);//压缩后长度17
        //压缩后的赫夫曼编码对应的字节数组[-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
        //System.out.println(Arrays.toString(huffmanCodeBytes));
        return huffmanCodeBytes;
    }

    /**
     * @Description:使用赫夫曼编码将原数组转换为新的赫夫曼编码压缩的字节数组
     * @Author: PABLO
     * @Date: 2022/4/1 15:58
     * @Params: [bytes 原始字符数组,必须将原数组传入，因为huffmanCode中的key和value编码是单独对应的，
     * 但是每个key可能会出现多次，每次都需要append一次value
     * huffmanCode 原始数组转换的赫夫曼编码，即每个字符对应的编码]
     * @Return: byte[]
     **/
    private byte[] zip(byte[] bytes, Map<Byte, String> huffmanCode) {

        StringBuilder stringBuilder = new StringBuilder();

        for (int i = 0; i < bytes.length; i++) {
            stringBuilder.append(huffmanCode.get(bytes[i]));
        }
        //统计赫夫曼编码对应的字节长度
        int len;
        //将二进制字符转为处理后的byte数组
        if (stringBuilder.length() % 8 == 0) {//刚好是整字节
            len = stringBuilder.length() / 8;
        } else {
            //这里+1是因为，如果不能被8整除，如等于6.3，向下取整，即6，
            // 但是实际是6点多，所以+1，即7
            len = stringBuilder.length() / 8 + 1;

        }

        byte[] huffmanCodeBytes = new byte[len];

        int byteArrIndex = 0;

        for (int i = 0; i < stringBuilder.length(); i += 8) {
            String strByte = "";
            //i+8可能大于stringBuilder长度，控制下表越界
            if (i + 8 > stringBuilder.length()) {
                strByte = stringBuilder.substring(i);//从i到结束

            } else {
                //步长8，每8位一字节
                strByte = stringBuilder.substring(i, i + 8);
            }
            //将得到的8位0101转为byte，然后放到返回值数组中  TODO 当最后截取的值是001或01的时候会转成byte=1,就会丢失0,就恢复不了
            huffmanCodeBytes[byteArrIndex++] = (byte) Integer.parseInt(strByte, 2);//这里的2代表输出该2进制数对应的10进制的数
        }

        // System.out.println("---" + stringBuilder.toString());


        return huffmanCodeBytes;
    }

    /**
     * @Description:getCodes（） 对外重载
     * @Author: PABLO
     * @Date: 2022/4/1 21:33
     * @Params: [node]
     * @Return: java.util.Map<java.lang.Byte, java.lang.String>
     **/
    private Map<Byte, String> getCodes(Node node) {
        return getCodes(node, "", stringBuilder);
    }

    /**
     * @Description: 获得每个字符对应的赫夫曼编码
     * @Author: PABLO
     * @Date: 2022/4/1 15:18
     * @Params: [node 赫夫曼树头结点,
     * code 某个叶子节点的路径,左子节点0  右子节点1
     * stringBuilder 用于拼接该叶子节点的路径]
     * @Return: void
     **/
    private Map<Byte, String> getCodes(Node node, String code, StringBuilder stringBuilder) {

        StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);

        stringBuilder2.append(code);

        if (node != null) {//处理
            if (node.data == null) {//字符为空非叶子节点
                //递归
                // 左
                getCodes(node.left, "0", stringBuilder2);
                //右
                getCodes(node.right, "1", stringBuilder2);
            } else {
                //叶子节点，将拼接好的路径编码存储
                huffmanCode.put(node.data, stringBuilder2.toString());
            }
        }

        return huffmanCode;


    }


    /**
     * @Description: 前序遍历
     * @Author: PABLO
     * @Date: 2022/4/1 21:31
     * @Params: [node]
     * @Return: void
     **/
    private void preOrder(Node node) {

        if (node != null) {
            node.preOrder();
        } else {
            System.out.println("root is null!");
        }
    }

    /**
     * @Description: 打印赫夫曼编码
     * @Author: PABLO
     * @Date: 2022/4/1 21:31
     * @Params: [huffmanCode]
     * @Return: void
     **/
    private void printHuffmanCode(Map<Byte, String> huffmanCode) {

        for (Map.Entry<Byte, String> byteStringEntry : huffmanCode.entrySet()) {
            System.out.println(byteStringEntry.getKey() + "--" + byteStringEntry.getValue());
        }
    }

    /**
     * @Description: 将原始字节数组转为对应的节点集合
     * @Author: PABLO
     * @Date: 2022/4/1 21:32
     * @Params: [content： 原始字节数组]
     * @Return: java.util.List<com.learn.data.tree.huff.Node>
     **/
    private List<Node> convert(byte[] content) {

        List<Node> list = new ArrayList<>();


        //创建map记录每个字符出现的次数
        Map<Byte, Integer> map = new HashMap<>();

        for (int i = 0; i < content.length; i++) {
            //先获取
            Integer count = map.get(content[i]);
            if (Objects.isNull(count)) {
                map.put(content[i], 1);
            } else {
                map.put(content[i], count + 1);
            }
        }

        //map转list
        for (Map.Entry<Byte, Integer> byteIntegerEntry : map.entrySet()) {
            list.add(new Node(byteIntegerEntry.getKey(), byteIntegerEntry.getValue()));
        }


        return list;
    }

    /**
     * @Description: 根据节点集合构建赫夫曼树
     * @Author: PABLO
     * @Date: 2022/4/1 21:32
     * @Params: [list： 节点集合]
     * @Return: com.learn.data.tree.huff.Node
     **/

    private Node getHuffmanTreeByList(List<Node> list) {

        while (list.size() > 1) {
            //排序
            Collections.sort(list);
            Node left = list.get(0);
            Node right = list.get(1);

            //只有权值，没有data
            Node node = new Node(null, left.weight + right.weight);

            node.left = left;

            node.right = right;

            list.remove(left);

            list.remove(right);

            list.add(node);
        }

        return list.get(0);
    }

}


class Node implements Comparable<Node> { //实现对象排序Collections.sort()
    Byte data;//数据本身，如 'a' ==> 97......即字符对应的ASCII编码

    int weight;//权重

    Node left;

    Node right;


    public Node(Byte data, int weight) {
        this.weight = weight;
        this.data = data;
    }

    public void preOrder() {
        System.out.println(this);
        if (this.left != null) this.left.preOrder();
        if (this.right != null) this.right.preOrder();
    }

    @Override
    public String toString() {
        return "Nodes{" +
                "data" + data + "-------" +
                "weight=" + weight +
                '}';
    }

    @Override
    public int compareTo(Node o) {
        return this.weight - o.weight;
    }
}


